class NumMatrix:

    def __init__(self, matrix):
        self.zero = False
        if len(matrix) == 0 or len(matrix[0]) == 0:
            self.zero = True
            return
        self.dp = [[0 for y in range(len(matrix[x]))] for x in range(len(matrix))]
        for i in range(len(matrix[0])):
            if i == 0:
                self.dp[0][i] = matrix[0][i]
            else:
                self.dp[0][i] = self.dp[0][i-1] + matrix[0][i]
        for j in range(1, len(matrix)):
            tmp = 0
            for i in range(len(matrix[j])):
                if i == 0:
                    self.dp[j][i] = self.dp[j-1][i] +  matrix[j][i] + tmp
                else:
                    self.dp[j][i] = self.dp[j -1][i] + matrix[j][i] + tmp
                tmp = tmp + matrix[j][i]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        if self.zero:
            return 0
        return self.dp[row2][col2] + self.getDbVal(row1-1, col1-1) - self.getDbVal(row2, col1-1) - self.getDbVal(row1-1, col2)

    def getDbVal(self, row, col):
        if row<0 or col<0:
            return 0
        return self.dp[row][col]

if __name__ == '__main__':
    matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
    so = NumMatrix(matrix)
    print(so.sumRegion(2, 1, 4, 3))
